Software developers use various persistent data structures or database implementations to store and organize data. Within these databases, individual data values are often grouped into data blocks, which are used as units of transfer to and from persistent storage such as disk, flash, or network storage. Each data block has a data type called a pointer associated with it that contains the data block's memory address. Specific data values can be obtained from the database by: (1) dereferencing pointers to find referenced data blocks, (2) retrieving the data blocks from persistent storage, and (3) parsing the data blocks to find the data values.
FIG. 1 illustrates a conventional database structure as discussed above. Individual data values (109) in the database are often grouped into data blocks (111) containing key→value pairs. As shown in FIG. 1, the data blocks can include key→value pairs where the keys are people's names and the values are the people's dates of birth. Each data block has a pointer (101a, 101b) associated with it that contains the data block's memory address for retrieving the data block. A conventional data retrieval would include: (1) dereferencing the pointer; (2) loading the associated data block into memory; and (3) parsing the loaded data block to find the desired key→value pair(s).
For example, a conventional search to find “all the people born in 1966” in the database structure of FIG. 1 requires that each pointer (101a, 101b) to a data block (111a, 111b) in the database be dereferenced to find each pointer's data block. Each data block (111a, 111b) is then retrieved from persistent storage and parsed to find the key→value pairs having “1966” as the birth year of their date of birth value. This process continues until all of the data blocks are retrieved and parsed. In FIG. 1, the first data block (111a) contains key→value pairs with birth years of 1954, 1964, 1977, 1978, and 1985. However, the conventional retrieval process requires the retrieving and parsing this data block even though the birth year “1966” will not be in the data block. Accessing persistent storage is time-consuming and expensive for computer applications.